1. Field of the Invention
The invention relates to encoding and decoding digital video signals, and more particularly, to the parallel calculation of prediction bits in a spatially predicted coded block pattern.
2. Description of the Prior Art
Full-motion video displays using analog video signals have long been available in the form of television. With recent advances in computer processing capabilities and affordability, full-motion video displays using digital video signals are becoming more widely available. Digital video systems provide significant improvements over conventional analog video systems in creating, modifying, transmitting, storing, and playing full-motion video sequences.
Digital video displays include large numbers of image frames that are played or rendered successively at frequencies of between 30 and 75 Hz. Each image frame is a still image formed from an array of pixels based on the display resolution of a particular system. As examples, VHS-based systems have display resolutions of 320 pixels wide by 480 pixels high, NTSC-based systems have display resolutions of 720 pixels wide by 486 high, and high-definition television (HDTV) systems have display resolutions of 1360 pixels wide by 1024 pixels high.
The amounts of raw digital information included in video sequences are massive. Storage and transmission of these amounts of video information is infeasible with conventional personal computer equipment. Consider, for example, a digitized form of a relatively low resolution VHS image format having a 320×480 pixel resolution. A full-length motion picture of two hours in duration at this resolution corresponds to 100 gigabytes of digital video information. By comparison, conventional compact optical disks have capacities of about 0.6 gigabytes, magnetic hard disks have capacities of 1-2 gigabytes, and compact optical disks under development have capacities of up to 8 gigabytes.
To address the limitations in storing and transmitting such massive amounts of digital video information, various video compression standards or processes have been established, including MPEG-1, MPEG-2, MPEG-4, and H.26X. These video compression techniques utilize similarities between successive image frames, referred to as temporal or interframe correlation, to provide interframe compression in which motion data and error signals are used to encode changes between frames.
In addition, conventional video compression techniques utilize similarities within image frames, referred to as intraframe correlation, to provide intraframe compression in which the image samples within an image frame are compressed. Intraframe compression is based upon conventional processes for compressing still images, such as discrete cosine transform (DCT) encoding. This type of coding is sometimes referred to as “texture” or “transform” coding. A “texture” generally refers to a two-dimensional array of image sample values, such as an array of chrominance and luminance values or an array of alpha (opacity) values. The term “transform” in this context refers to how the image samples are transformed into spatial frequency components during the coding process. This use of the term “transform” should be distinguished from a geometric transform used to estimate scene changes in some interframe compression methods.
Spatially predicted coded block patterns have been proposed as an improvement to the conventional intraframe coding standards. In a spatially predicted based intraframe, a macroblock includes four luminance blocks and an associated spatially predicted coded block pattern. The coded block pattern has four bits used for indicating which of the luminance blocks in the macroblock are coded in the bitstream using DCT encoding. To encode a spatially predicted coded block pattern, prediction bits for each bit in the coded block pattern are calculated, each bit in the coded block pattern is XORed with its prediction bit, and the resulting bit pattern forms a spatially predicted coded block pattern. A lookup table is used to convert the convert the spatially predicted coded block pattern to a variable length code for transmission or storage. The reverse procedure is used to decode the variable length code. A lookup table is used to convert the variable length code to a spatially predicted coded block pattern. Prediction bits are calculated for each bit in the spatially predicted coded block pattern and each bit in the spatially predicted coded block pattern is then XORed with its prediction bit.
FIG. 1 shows a coded block pattern 100 according to the prior art. The coded block pattern 100 includes an A0 bit, an A1 bit, an A2 bit, and an A3 bit. During the encoding and decoding process of a spatially predicted coded block pattern, a prediction bit must be calculated for each bit in the coded block pattern 100. The prediction bit calculations use a D0 bit, an X0 bit, an X1 bit, a Y0 bit, and a Y1 bit, which are adjacent bits to the coded block pattern 100. The D0 bit, the X0 bit, and the X1 bit indicate which blocks in a first row are coded in the bitstream, the Y0 bit, the A0 bit, and the A1 bit indicate which blocks in a second row are coded in the bitstream, and the Y1 bit, the A2 bit, and the A3 bit indicate which blocks in a third row are coded in the bitstream. There are also additional bits to the left and right in each row and additional rows above and below the three rows shown; but as these bits are not used in the prediction bit calculations, they have been omitted from FIG. 1.
To calculate the prediction bits for A0, A1, A2, A3 the following steps are performed in the order shown:
Step 1.If the X0 bit is equivalent to the D0 bit, the A0 bit is set equal to the Y0 bit, otherwise the A0 bit is set equal to the X0 bit.
Step 2.If the X1 bit is equivalent to the X0 bit, the A1 bit is set equal to the A0 bit, otherwise the A1 bit is set equal to the X1 bit.
Step 3.If the A0 bit is equivalent to the Y0 bit, the A2 bit is set equal to the Y1 bit, otherwise the A2 bit is set equal to the A0 bit.
Step 4.If the A1 bit is equivalent to the A0 bit, the A3 bit is set equal to the A2 bit, otherwise the A3 bit is set equal to the A1 bit.
Because each successive step depends on the result of the previous step, the steps must be executed one after another. When implemented in hardware, this typically means a minimum of four clock cycles to calculate the prediction bits for a coded block pattern 100, one clock cycle being used for each step. It would be beneficial to reduce the required clock cycles, however, if the steps are grouped together using combinatorial logic into a single clock cycle, the time delay from the start of the calculation to the completion of each bit (A0, A1, A2, A3) takes a large number of gate delays and may not meet the timing constraints of a system having a high system clock frequency. Additionally a large amount of gates are used. A faster and more efficient implementation of the prediction bit calculations is needed.